package org.tamal.java;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * The Sudoku solver.
 * @author Tamal Kanti Nath
 */
public final class Sudoku {

    private final Cell[] cells = new Cell[81];
    private final Group[] row = new Group[9];
    private final Group[] col = new Group[9];
    private final Group[] box = new Group[9];

    /**
     * Creates a Sudoku object using numbers.
     * @param numbers the numbers
     */
    public Sudoku(List<Integer> numbers) {
        if (numbers.size() != cells.length) {
            throw new RuntimeException("Incorrect number of integers passed");
        }
        for (int i = 0; i < 9; ++i) {
            row[i] = new Group('r', i);
            col[i] = new Group('c', i);
            box[i] = new Group('b', i);
        }
        for (int i = 0; i < cells.length; ++i) {
            int r = i / 9;
            int c = i % 9;
            int b = (r / 3) * 3 + c / 3;
            cells[i] = new Cell(row[r], col[c], box[b]);
        }
        for (int i = 0; i < cells.length; ++i) {
            int value = numbers.get(i);
            if (value != 0) {
                cells[i].setValue(value);
            }
        }
    }

    /**
     * Main method i.e. entry point.
     * @param args arguments
     */
    public static void main(String[] args) {
        Sudoku sudoku;
        String file = "target/classes/sudoku.txt";
        List<Integer> numbers = new ArrayList<>(81);
        try (InputStream is = new FileInputStream(file)) {
            int ch;
            while ((ch = is.read()) != -1) {
                if (ch < '0' || ch > '9') {
                    continue;
                }
                numbers.add(ch - '0');
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        sudoku = new Sudoku(numbers);
        System.out.println(sudoku);
        sudoku.solve();
    }

    /**
     * Solve the Sudoku game.
     */
    public void solve() {
        int count;
        do {
            count = updateSingleCandidates();
            if (count == 0) {
                count = updateUniqueCandidates();
            }
            if (count == 0) {
                count = findNakedCandidates(2);
            }
            if (count == 0) {
                count = findLockedCandidate();
            }
            if (count == 0) {
                count = findXYZWingCandidates();
            }
            if (count == 0) {
                count = findXYWingCandidates();
            }
            if (count == 0) {
                count = findHiddenCandidates(2);
            }
            if (count == 0) {
                count = findNakedCandidates(3);
            }
            if (count == 0) {
                count = findHiddenCandidates(3);
            }
            if (count == 0) {
                count = findNakedCandidates(4);
            }
            if (count == 0) {
                count = findHiddenCandidates(4);
            }
            if (count == 0) {
                count = findFishCandidates(2);
            }
            if (count == 0) {
                count = findFishCandidates(3);
            }
            if (count == 0) {
                count = findFishCandidates(4);
            }
            if (count != 0) {
                System.out.println(this);
            }
        } while (count != 0);
    }

    private int updateSingleCandidates() {
        int count = 0;
        for (Cell cell : cells) {
            if (cell.getCandidates().size() == 1) {
                cell.setValue(cell.getCandidates().iterator().next());
                ++count;
                log("SingleCandidate", cell);
            }
        }
        return count;
    }

    private int updateUniqueCandidates() {
        int count = 0;
        for (int i = 0; i < 9 && count == 0; ++i) {
            count += row[i].updateUniqueCandidates();
            count += col[i].updateUniqueCandidates();
            count += box[i].updateUniqueCandidates();
        }
        return count;
    }

    private int findLockedCandidate() {
        int count = 0;
        for (int c = 1; c <= 9 && count == 0; ++c) {
            for (int i = 0; i < 9 && count == 0; ++i) {
                count += row[i].findLockedCandidate(c);
                count += col[i].findLockedCandidate(c);
            }
        }
        return count;
    }

    private int findNakedCandidates(int n) {
        int count = 0;
        for (int i = 0; i < 9 && count == 0; ++i) {
            count += row[i].findNakedCandidates(n);
            count += col[i].findNakedCandidates(n);
            count += box[i].findNakedCandidates(n);
        }
        return count;
    }

    private int findHiddenCandidates(int n) {
        int count = 0;
        for (int i = 0; i < 9 && count == 0; ++i) {
            count += row[i].findHiddenCandidates(n);
            count += col[i].findHiddenCandidates(n);
            count += box[i].findHiddenCandidates(n);
        }
        return count;
    }

    private int findFishCandidates(int n) {
        int count = 0;
        for (List<Integer> combination : getCombination(n, 9)) {
            List<Group> group = new ArrayList<>();
            for (int i : combination) {
                group.add(row[i]);
            }
            for (int c = 1; c <= 9 && count == 0; ++c) {
                count += Group.findFishCandidates(c, group);
            }
            group.clear();
            for (int i : combination) {
                group.add(col[i]);
            }
            for (int c = 1; c <= 9 && count == 0; ++c) {
                count += Group.findFishCandidates(c, group);
            }
        }
        return count;
    }

    private int findXYWingCandidates() {
        for (Cell xy : cells) {
            if (xy.getCandidates().size() != 2) {
                continue;
            }
            Iterator<Integer> i = xy.getCandidates().iterator();
            int x = i.next();
            int y = i.next();
            for (Cell xz : xy.getNeighbors(x)) {
                if (xz.getCandidates().size() != 2 || xy.compareTo(xz) == 0) {
                    continue;
                }
                i = xz.getCandidates().iterator();
                int z = i.next();
                if (x == z) {
                    z = i.next();
                }
                for (Cell yz : xy.getNeighbors(y)) {
                    if (yz.getCandidates().size() != 2) {
                        continue;
                    }
                    if (!yz.getCandidates().contains(z)) {
                        continue;
                    }
                    List<Cell> list = xz.getNeighbors(z);
                    list.retainAll(yz.getNeighbors(z));
                    list.remove(xy);
                    for (Cell cell : list) {
                        cell.remove(z);
                        log("XY-Wing xy=" + xy + ", xz=" + xz + ", yz=" + yz,
                                cell);
                        return 1;
                    }
                }
            }
        }
        return 0;
    }

    private int findXYZWingCandidates() {
        for (Cell xy : cells) {
            if (xy.getCandidates().size() != 2) {
                continue;
            }
            Iterator<Integer> i = xy.getCandidates().iterator();
            int x = i.next();
            int y = i.next();
            for (Cell xyz: xy.getNeighbors(x)) {
                Set<Integer> c = new TreeSet<>(xyz.getCandidates());
                if (c.size() != 3 || !c.contains(y)) {
                    continue;
                }
                c.removeAll(xy.getCandidates());
                int z = c.iterator().next();
                for (Cell xz: xyz.getNeighbors(x)) {
                    c = xz.getCandidates();
                    if (c.size() != 2 || !c.contains(z)) {
                        continue;
                    }
                    List<Cell> list = xyz.getNeighbors(0);
                    list.retainAll(xy.getNeighbors(0));
                    list.retainAll(xz.getNeighbors(0));
                    int count = 0;
                    for (Cell cell : list) {
                        if (cell.getCandidates().removeAll(xyz.getCandidates())) {
                            ++count;
                            log("XYZ-Wing xy=" + xy + ", xz=" + xz
                                    + ", xyz=" + xyz, cell);
                        }
                    }
                    if (count != 0) {
                        return count;
                    }
                }
            }
        }
        return 0;
    }

    /**
     * Returns a combination of n numbers from the range 0 to k - 1.
     * @param k the size of each combination
     * @param n the number of elements
     * @return combinations
     */
    static List<List<Integer>> getCombination(int k, int n) {
        if (k < 1 || k > n) {
            throw new RuntimeException("Invalid Size: " + k);
        }
        List<List<Integer>> combination = new ArrayList<>();
        if (k == 1) {
            for (int i = 0; i < n; ++i) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                combination.add(list);
            }
            return combination;
        }
        for (List<Integer> list : getCombination(k - 1, n)) {
            for (int i = list.get(list.size() - 1) + 1; i < n; ++i) {
                List<Integer> newList = new ArrayList<>(list);
                newList.add(i);
                combination.add(newList);
            }
        }
        return combination;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < cells.length; ++i) {
            if (i % 9 == 0) {
                sb.append('\n');
            }
            sb.append(cells[i].getString() + "\t");
        }
        return sb.toString();
    }

    /**
     * Log cell value update.
     * @param from the source of the update
     * @param cell the cell
     */
    static void log(String from, Cell cell) {
        System.out.println(from + ", Cell: " + cell);
    }

    /**
     * Represents a cell in sudoku.
     * @author Tamal Kanti Nath
     */
    static class Cell implements Comparable<Cell> {
        private int value;
        private final Set<Integer> candidates = new TreeSet<>();
        private final Group row;
        private final Group col;
        private final Group box;

        /**
         * Creates a cell.
         * @param box the row
         * @param col the column
         * @param row the 3x3 box
         */
        public Cell(Group row, Group col, Group box) {
            this.row = row;
            this.col = col;
            this.box = box;
            row.add(this);
            col.add(this);
            box.add(this);
            for (int i = 1; i <= 9; ++i) {
                candidates.add(i);
            }
        }

        /**
         * Returns the values.
         * @return the value
         */
        public int getValue() {
            return value;
        }

        /**
         * Sets the values.
         * @param value the value to set
         */
        public void setValue(int value) {
            this.value = value;
            candidates.clear();
            for (Cell cell : getNeighbors(value)) {
                cell.remove(value);
            }
        }

        /**
         * Returns the option.
         * @return the option
         */
        public Set<Integer> getCandidates() {
            return candidates;
        }

        /**
         * Returns the option.
         * @param c the candidate
         * @return the option
         */
        public boolean remove(int c) {
            return candidates.remove(c);
        }

        /**
         * Returns the row.
         * @return the row
         */
        public Group getRow() {
            return row;
        }

        /**
         * Returns the column.
         * @return the col
         */
        public Group getCol() {
            return col;
        }

        /**
         * Returns the 3x3 box.
         * @return the box
         */
        public Group getBox() {
            return box;
        }

        /**
         * Returns neighborhood cells having given candidate from it's row,
         * column and box. If the candidate is 0 then all the cells are
         * returned.
         * @param c the neighbors having this candidate
         * @return list of cells
         */
        public List<Cell> getNeighbors(int c) {
            List<Cell> list = new ArrayList<>(box.getCells(c));
            for (Cell cell : row.getCells(c)) {
                if (!list.contains(cell)) {
                    list.add(cell);
                }
            }
            for (Cell cell : col.getCells(c)) {
                if (!list.contains(cell)) {
                    list.add(cell);
                }
            }
            list.remove(this);
            return list;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Cell) {
                Cell cell = (Cell) obj;
                if (row.equals(cell.row) && col.equals(cell.col)) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public int compareTo(Cell cell) {
            return hashCode() - cell.hashCode();
        }

        @Override
        public int hashCode() {
            int hash = 10000 * value;
            for (int c : candidates) {
                hash += c * c * c;
            }
            return hash;
        }

        /**
         * Gets a string representation of the cell.
         * @return value or options for the string
         */
        public String getString() {
            StringBuffer sb = new StringBuffer();
            if (value == 0) {
                for (Integer c : candidates) {
                    sb.append(c);
                }
            } else {
                sb.append("(" + value + ")");
            }
            return sb.toString();
        }

        @Override
        public String toString() {
            return getString() + " ["
                    + (row.getNumber() + 1) + ", "
                    + (col.getNumber() + 1) + "]";
        }

    }

    /**
     * Represents a row or column or 3x3 box in sudoku.
     * @author Tamal Kanti Nath
     */
    static class Group implements Comparable<Group> {
        private final int number;
        private final List<Cell> cells = new ArrayList<>();
        private char type;

        /**
         * Create Group with number.
         * @param type the Group type
         * @param number the Group number
         */
        public Group(char type, int number) {
            this.type = type;
            this.number = number;
        }

        /**
         * Returns the cells in a new list.
         * @return the cells
         */
        public List<Cell> getCells() {
            return new ArrayList<>(cells);
        }

        /**
         * Returns the Group number.
         * @return Group number
         */
        public int getNumber() {
            return number;
        }

        /**
         * Add a cell.
         * @param cell the cell to add
         */
        public void add(Cell cell) {
            cells.add(cell);
        }

        /**
         * Remove the option from this Group cells.
         * @param option the option to remove
         * @return number of options removed.
         */
        public int remove(int option) {
            int count = 0;
            for (Cell cell : cells) {
                if (cell.remove(option)) {
                    ++count;
                }
            }
            return count;
        }

        /**
         * Returns cells having given option. If the candidate is 0 then all the
         * cells are returned.
         * @param c the candidate
         * @return the cells having the option
         */
        public List<Cell> getCells(int c) {
            if (c == 0) {
                return new ArrayList<>(cells);
            }
            List<Cell> match = new ArrayList<>();
            for (Cell cell : cells) {
                if (cell.getCandidates().contains(c)) {
                    match.add(cell);
                }
            }
            return match;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Group) {
                Group group = (Group) obj;
                return type == group.type && number == group.number;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return type ^ number;
        }

        @Override
        public String toString() {
            String str = null;
            if (type == 'r') {
                str = "Row ";
            }
            if (type == 'c') {
                str = "Column ";
            }
            if (type == 'b') {
                str = "Box ";
            }
            return str + (number + 1);
        }

        @Override
        public int compareTo(Group group) {
            return number - group.number;
        }

        /**
         * Update hidden singles.
         * @return number of updates
         */
        int updateUniqueCandidates() {
            int count = 0;
            for (int i = 1; i <= 9; ++i) {
                List<Cell> c = getCells(i);
                if (c.size() == 1) {
                    c.get(0).setValue(i);
                    ++count;
                    log("UniqueCandidate in " + this, c.get(0));

                }
            }
            return count;
        }

        /**
         * Find locked candidate and remove options.
         * This method is only applicable for row and columns.
         * @param c the candidate to search
         * @return number of options removed.
         */
        int findLockedCandidate(int c) {
            int count = 0;
            Map<Group, List<Cell>> map = new TreeMap<>();
            for (Cell cell : getCells(c)) {
                List<Cell> list = map.get(cell.getBox());
                if (list == null) {
                    list = new ArrayList<>();
                    map.put(cell.getBox(), list);
                }
                list.add(cell);
            }
            if (map.size() == 1) {
                List<Cell> list = map.keySet().iterator().next().getCells(c);
                list.removeAll(getCells(c));
                for (Cell cell : list) {
                    if (cell.remove(c)) {
                        ++count;
                        log("LockedCandidate " + c + " in " + this, cell);
                    }
                }
            }
            boolean found = false;
            for (Map.Entry<Group, List<Cell>> entry : map.entrySet()) {
                if (entry.getKey().getCells(c).size()
                        == entry.getValue().size()) {
                    map.remove(entry.getKey());
                    found = true;
                    break;
                }
            }
            if (found) {
                for (List<Cell> list : map.values()) {
                    for (Cell cell : list) {
                        cell.remove(c);
                        ++count;
                        log("LockedCandidates " + c + " in " + this, cell);
                    }
                }
            }
            return count;
        }

        /**
         * Find hidden pairs and remove options.
         * @param n the number of cells to taken for combination
         * @return number of options removed.
         */
        int findHiddenCandidates(int n) {
            int count = 0;
        OUTER:
            for (int i = 1; i <= 9; ++i) {
                List<Cell> list = getCells(i);
                if (list.size() != n) {
                    continue;
                }
                List<Integer> common = new ArrayList<>();
                for (int j = 1; j <= 9; ++j) {
                    common.add(j);
                }
                for (Cell cell : list) {
                    common.retainAll(cell.getCandidates());
                }
                if (common.size() != n) {
                    continue;
                }
                for (int j : common) {
                    if (getCells(j).size() == n) {
                        continue OUTER;
                    }
                }
                for (Cell cell : list) {
                    if (cell.getCandidates().retainAll(common)) {
                        ++count;
                        log ("HiddenCandidates " + common + " in " + this, cell);
                    }
                }
            }
            return count;
        }

        private List<List<Cell>> getCombination(int n) {
            List<List<Cell>> combination = new ArrayList<>();
        OUTER:
            for (List<Integer> list : Sudoku.getCombination(n, 9)) {
                List<Cell> c = new ArrayList<>();
                for (int i : list) {
                    if (cells.get(i).getValue() != 0) {
                        continue OUTER;
                    }
                    c.add(cells.get(i));
                }
                combination.add(c);
            }
            return combination;
        }

        /**
         * Find naked candidates and remove options.
         * @param n the number of cells to taken for combination
         * @return number of options removed.
         */
        int findNakedCandidates(int n) {
            int count = 0;
            for (List<Cell> combination : getCombination(n)) {
                Set<Integer> common = new TreeSet<>();
                for (Cell c : combination) {
                    common.addAll(c.getCandidates());
                }
                if (common.size() != n) {
                    continue;
                }
                List<Cell> list = getCells();
                list.removeAll(combination);
                for (Cell cell : list) {
                    if (cell.getCandidates().removeAll(common)) {
                        ++count;
                        log("NakedCandidates " + common + " in " + this, cell);
                    }
                }
            }
            return count;
        }

        /**
         * Find XWing / Swordfish / Jellyfish candidates and remove options.
         * @param c the candidate to search
         * @param groups rows or columns
         * @return number of options removed.
         */
        static int findFishCandidates(int c, List<Group> groups) {
            Set<Group> group = new TreeSet<>();
            List<List<Cell>> lists = new ArrayList<>();
            for (Group g : groups) {
                List<Cell> list = g.getCells(c);
                if (list.size() == 0 || list.size() > groups.size()) {
                    return 0;
                }
                lists.add(list);
                for (Cell cell : list) {
                    group.add(g.type == 'r' ? cell.getCol() : cell.getRow());
                }
            }
            if (group.size() != groups.size()) {
                return 0;
            }
            int count = 0;
            List<Cell> list = new ArrayList<>();
            for (Group g : group) {
                list.addAll(g.getCells(c));
            }
            for (List<Cell> l : lists) {
                list.removeAll(l);
            }
            for (Cell cell : list) {
                cell.remove(c);
                ++count;
                log("FishCandidate " + c + " in " + groups, cell);
            }
            return count;
        }

    }
}
